package com.LeeCode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 二叉搜索树中的众数
 */

public class Code501 {
    public static void main(String[] args) {
        Integer[] arr = {1, null, 2, 2};
        TreeNode root = Utils.buildTree(arr);
        System.out.println(Arrays.toString(new Code501().findMode(root)));
    }

    private int count = 0;       // 当前值的出现次数
    private int maxCount = 0;    // 最大出现次数
    private Integer prev = null; // 前一个值
    private List<Integer> result = new ArrayList<>();

    public int[] findMode(TreeNode root) {
        dfs(root);
        return result.stream().mapToInt(i -> i).toArray();
    }

    private void dfs(TreeNode root) {
        if (root == null) return;
        dfs(root.left);
        if (prev != null && root.val == prev) {
            count++;
        } else {
            count = 1;
        }
        prev = root.val;

        if (count > maxCount) {
            maxCount = count;
            result.clear();
            result.add(root.val);
        } else if (count == maxCount) {
            result.add(root.val);
        }

        dfs(root.right);
    }
}
